{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Queries on Number of Points Inside a Circle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计一个圆中点的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>points</code> ，其中 <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> ，表示第 <code>i</code> 个点在二维平面上的坐标。多个点可能会有 <strong>相同</strong> 的坐标。</p>\n",
    "\n",
    "<p>同时给你一个数组 <code>queries</code> ，其中 <code>queries[j] = [x<sub>j</sub>, y<sub>j</sub>, r<sub>j</sub>]</code> ，表示一个圆心在 <code>(x<sub>j</sub>, y<sub>j</sub>)</code> 且半径为 <code>r<sub>j</sub></code><sub> </sub>的圆。</p>\n",
    "\n",
    "<p>对于每一个查询 <code>queries[j]</code> ，计算在第 <code>j</code> 个圆 <strong>内</strong> 点的数目。如果一个点在圆的 <strong>边界上</strong> ，我们同样认为它在圆 <strong>内</strong> 。</p>\n",
    "\n",
    "<p>请你返回一个数组<em> </em><code>answer</code> ，其中<em> </em><code>answer[j]</code>是第 <code>j</code> 个查询的答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/25/chrome_2021-03-25_22-34-16.png\" style=\"width: 500px; height: 418px;\">\n",
    "<pre><b>输入：</b>points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]\n",
    "<b>输出：</b>[3,2,2]\n",
    "<b>解释：</b>所有的点和圆如上图所示。\n",
    "queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/25/chrome_2021-03-25_22-42-07.png\" style=\"width: 500px; height: 390px;\">\n",
    "<pre><b>输入：</b>points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]\n",
    "<b>输出：</b>[2,3,2,4]\n",
    "<b>解释：</b>所有的点和圆如上图所示。\n",
    "queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆，queries[3] 是紫色的圆。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 500</code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>​​​​​​i</sub>, y<sub>​​​​​​i</sub> &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 500</code></li>\n",
    "\t<li><code>queries[j].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= x<sub>j</sub>, y<sub>j</sub> &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= r<sub>j</sub> &lt;= 500</code></li>\n",
    "\t<li>所有的坐标都是整数。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [queries-on-number-of-points-inside-a-circle](https://leetcode.cn/problems/queries-on-number-of-points-inside-a-circle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [queries-on-number-of-points-inside-a-circle](https://leetcode.cn/problems/queries-on-number-of-points-inside-a-circle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3],[3,3],[5,3],[2,2]]\\n[[2,3,1],[4,3,1],[1,1,2]]', '[[1,1],[2,2],[3,3],[4,4],[5,5]]\\n[[1,2,2],[2,2,2],[4,3,2],[4,3,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answer=[]\n",
    "        for query in queries:\n",
    "            ans=0\n",
    "            for point in points:\n",
    "                if (query[0]-point[0])**2+(query[1]-point[1])**2<=query[2]**2:\n",
    "                    ans+=1\n",
    "            answer.append(ans)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        a=[]\n",
    "        for l in range(len(queries)):\n",
    "            a.append(0)\n",
    "            for point in points:\n",
    "                if (point[0]-queries[l][0])**2+(point[1]-queries[l][1])**2<=queries[l][2]**2:\n",
    "                    a[l]+=1\n",
    "        return a\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answers = [0]*len(queries)\n",
    "\n",
    "        for i,circle in enumerate(queries):\n",
    "            xo, yo, r = circle\n",
    "            for point in points:\n",
    "                xp, yp = point\n",
    "\n",
    "                if (xp-xo)**2+(yp-yo)**2 <= r**2:\n",
    "                    answers[i] += 1\n",
    "        \n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        cases = len(queries)\n",
    "        result = [0 for __ in range(cases)]\n",
    "\n",
    "        for q in range(cases):\n",
    "            ex, ey, r = queries[q]\n",
    "            for px, py in points:\n",
    "                result[q] += int((px-ex) * (px-ex) + (py-ey) * (py-ey) <= r * r)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answers = [0]*len(queries)\n",
    "\n",
    "        for i,circle in enumerate(queries):\n",
    "            xo, yo, r = circle\n",
    "            count = 0\n",
    "            for point in points:\n",
    "                xp, yp = point\n",
    "\n",
    "                if (xp-xo)**2+(yp-yo)**2 <= r**2:\n",
    "                    count += 1\n",
    "            answers[i] = count\n",
    "        \n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        data = [0]*len(queries)\n",
    "        \n",
    "        for i in range(len(queries)):\n",
    "            for point in points:\n",
    "                if (point[0] - queries[i][0])**2 + (point[1] - queries[i][1])**2 <= queries[i][2]**2:\n",
    "                    data[i] = data[i] + 1\n",
    "            \n",
    "\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        for i, (m, n, r) in enumerate(queries):\n",
    "            NUM = complex(m, n)\n",
    "            queries[i] = 0\n",
    "            for x,y in points:\n",
    "                num = complex(x, y)\n",
    "                if abs(NUM - num) <= r:\n",
    "                    queries[i] += 1\n",
    "        return queries\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        length = len(queries)\n",
    "        res = {i: 0 for i in range(length)}\n",
    "        for index, querie in enumerate(queries):\n",
    "            for point in points:\n",
    "                d = math.sqrt((point[0] - querie[0])**2 + (point[1] - querie[1])**2)\n",
    "                if d <= querie[2]:\n",
    "                    res[index] += 1\n",
    "        return list(res.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answers = [0]*len(queries)\n",
    "\n",
    "        for i,circle in enumerate(queries):\n",
    "            xo, yo, r = circle\n",
    "            for point in points:\n",
    "                xp, yp = point\n",
    "\n",
    "                if (xp-xo)**2+(yp-yo)**2 <= r**2:\n",
    "                    answers[i] += 1\n",
    "        \n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        count_list=[]\n",
    "        for  query in queries:\n",
    "            x1=query[0]\n",
    "            y1=query[1]\n",
    "            r=query[2]\n",
    "            count=0\n",
    "            for point in points:\n",
    "                x=point[0]\n",
    "                y=point[1]\n",
    "                if ((x-x1)**2 +(y-y1)**2)**0.5 <= r:\n",
    "                    count+=1   \n",
    "                else:\n",
    "                    continue\n",
    "            count_list.append(count)\n",
    "        return count_list \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "        for i,(cx,cy,cr) in enumerate(queries):\n",
    "            for (px,py) in points:\n",
    "                if (cx - px)**2 + (cy - py)**2 <= cr**2:\n",
    "                    ans[i] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def distance(a, b):\n",
    "            return \n",
    "        for i, (ax, ay, r) in enumerate(queries):\n",
    "            r *= r\n",
    "            queries[i] = 0\n",
    "            for bx, by in points:\n",
    "                if (ax - bx) ** 2 + (ay - by) ** 2 <= r:\n",
    "                    queries[i] += 1\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answer=[0]*len(queries)\n",
    "        for i in range(len(queries)):\n",
    "            m,n,r = queries[i]\n",
    "            for x,y in points:\n",
    "                if (x-m)**2+(y-n)**2<=r**2:\n",
    "                    answer[i] = answer[i]+1\n",
    "        return answer\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        re = []\n",
    "        for j in range(len(queries)):\n",
    "            n = 0\n",
    "            rq = queries[j][2]**2\n",
    "            qx = queries[j][0]\n",
    "            qy = queries[j][1]\n",
    "            for i in range(len(points)):\n",
    "                if rq >= abs(points[i][0]-qx)**2 + abs(points[i][1]-qy)**2:\n",
    "                    n += 1\n",
    "            re.append(n)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answer = [0]*len(queries)\n",
    "        for i, (px, py) in enumerate(points):\n",
    "            for j, (qx, qy, qr) in enumerate(queries):\n",
    "                if (px-qx)**2 + (py-qy)**2 <= qr**2:\n",
    "                    answer[j] += 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        count_list=[]\n",
    "        for  query in queries:\n",
    "            x1=int(query[0])\n",
    "            y1=int(query[1])\n",
    "            r=int(query[2])\n",
    "            count=0\n",
    "            for point in points:\n",
    "                x=int(point[0])\n",
    "                y=int(point[1])\n",
    "                if pow((x-x1)**2 +(y-y1)**2,0.5) <= r:\n",
    "                    count+=1   \n",
    "                else:\n",
    "                    continue\n",
    "            count_list.append(count)\n",
    "        return count_list \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(queries)\n",
    "        res=[0]*n\n",
    "        for i in range(n):\n",
    "            for point in points:\n",
    "                if (point[0]-queries[i][0])**2+(point[1]-queries[i][1])**2<=queries[i][2]**2:\n",
    "                    res[i]+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "        for point in points:\n",
    "            for j, querie in enumerate(queries):\n",
    "                if (((querie[0] - point[0]) ** 2) + ((querie[1] - point[1]) ** 2) - querie[2] ** 2 <= 0):\n",
    "                    ans[j] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for i in queries:\n",
    "            x,y,r = i\n",
    "            count = 0\n",
    "            for j in points:\n",
    "                pointx,pointy = j\n",
    "                dx = x-pointx if x-pointx>=0 else pointx-x\n",
    "                dy = y-pointy if y-pointy>=0 else pointy-y\n",
    "                distance = dx*dx+dy*dy\n",
    "                if distance<=r*r:\n",
    "                    count += 1\n",
    "            res.append(count)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        length = len(queries)\n",
    "        res = {i: 0 for i in range(length)}\n",
    "        for index, querie in enumerate(queries):\n",
    "            for point in points:\n",
    "                d = ((point[0] - querie[0])**2 + (point[1] - querie[1])**2)\n",
    "                if d <= querie[2]**2:\n",
    "                    res[index] += 1\n",
    "        return list(res.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "        先判断点是不是在圆内\n",
    "        \"\"\"\n",
    "        def in_circle(circle,point):\n",
    "            x = circle[0]\n",
    "            y = circle[1]\n",
    "            r = circle[2]\n",
    "            x1 = point[0]\n",
    "            y1 = point[1]\n",
    "            if (x1 - x)**2 + (y1 - y)**2 <= r**2:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "        numlist = []\n",
    "        for i in queries:\n",
    "            steps = 0\n",
    "            for j in points:\n",
    "                if in_circle(i,j):\n",
    "                    steps += 1\n",
    "            numlist.append(steps)\n",
    "        return numlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            p = 0\n",
    "            r2 = q[2]**2\n",
    "            for o in points:\n",
    "                if (o[0] - q[0])**2 + (o[1]-q[1])**2 <= r2:\n",
    "                    p += 1\n",
    "            ans.append(p)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        count = 0 \n",
    "        output = []\n",
    "        for circle in queries:\n",
    "            x = circle[0]\n",
    "            y = circle[1]\n",
    "            r = circle[2]\n",
    "            for point in points:\n",
    "                xp = point[0]\n",
    "                yp = point[1]\n",
    "                if (xp-x)**2 + (yp-y)**2 <= r**2:\n",
    "                    count +=1\n",
    "            output.append(count)\n",
    "            count = 0\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(\n",
    "        self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for x, y, r in queries:\n",
    "            cnt = 0\n",
    "            for i, j in points:\n",
    "                dx, dy = i - x, j - y\n",
    "                cnt += dx * dx + dy * dy <= r * r\n",
    "            ans.append(cnt)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(points) # 点个数\n",
    "        m = len(queries) # 圆个数\n",
    "        ans = [0] * m\n",
    "        for j in range(m):\n",
    "            for i in range(n):\n",
    "                if (queries[j][0] - points[i][0])**2 + (queries[j][1] - points[i][1])**2 <= queries[j][2]**2:\n",
    "                    ans[j] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def distance(a, b):\n",
    "            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2\n",
    "        for i, (*a, r) in enumerate(queries):\n",
    "            r *= r\n",
    "            queries[i] = 0\n",
    "            for b in points:\n",
    "                if distance(a, b) <= r:\n",
    "                    queries[i] += 1\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = int(0)\n",
    "        answer = [0] * len(queries)\n",
    "        for x, y, r in queries:\n",
    "            for i, j in points:\n",
    "                if  abs(i-x) * abs(i-x) + abs(j -y) * abs(j -y) <= r * r:\n",
    "                    answer[n] += 1\n",
    "            n += 1\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(\n",
    "        self, points: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        ans = []\n",
    "        for x, y, r in queries:\n",
    "            cnt = 0\n",
    "            for i, j in points:\n",
    "                dx, dy = i - x, j - y\n",
    "                cnt += dx * dx + dy * dy <= r * r\n",
    "            ans.append(cnt)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        answer = []\n",
    "        for i in range(n):\n",
    "            count = 0\n",
    "            for j in range(len(points)):\n",
    "                a = (points[j][0] - queries[i][0])**2 + (points[j][1] - queries[i][1])**2\n",
    "                if a <= queries[i][2]**2:\n",
    "                    count = count + 1\n",
    "            answer.append(count)\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def distance_square(circle_center,point_position):\n",
    "            return (circle_center[0]-point_position[0])**2 + (circle_center[1]-point_position[1])**2\n",
    "        answer=[]\n",
    "        for each in queries:\n",
    "            count = 0\n",
    "            for each_point in points:\n",
    "                if distance_square(each,each_point) <= each[2]**2:\n",
    "                    count += 1\n",
    "            answer.append(count)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''def__init__(self,points,queries):\n",
    "        points=self.points\n",
    "        queries=self.queries'''\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        self.points=points\n",
    "        self.queries=queries\n",
    "        result=[] \n",
    "        for query in self.queries:\n",
    "            xi=query[0]\n",
    "            yi=query[1]\n",
    "            r=query[2]\n",
    "            i=0\n",
    "            for point in self.points:\n",
    "                x=point[0]\n",
    "                y=point[1]\n",
    "                if (x-xi)*(x-xi)+(y-yi)*(y-yi)<=r*r:\n",
    "                    i=i+1\n",
    "                else:\n",
    "                    pass\n",
    "            result.append(i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for x, y, z in queries:\n",
    "            圆点数 = 0\n",
    "            z *= z\n",
    "            z += 1\n",
    "            for i, j in points:\n",
    "                i, j = i-x, j-y\n",
    "                圆点数 += i*i + j*j < z\n",
    "            append(圆点数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        for i, (cx, cy, cr) in enumerate(queries):\n",
    "            for (px, py) in points:\n",
    "                if (cx - px) ** 2 + (cy - py) ** 2 <= cr ** 2:\n",
    "                    ans[i] += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        for i, (cx, cy, cr) in enumerate(queries):\n",
    "            for (px, py) in points:\n",
    "                if (cx - px) ** 2 + (cy - py) ** 2 <= cr ** 2:\n",
    "                    ans[i] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [0]*n\n",
    "\n",
    "        for i, (x,y,r) in enumerate(queries):\n",
    "            for x1,y1 in points:\n",
    "                if (x-x1)**2 + (y-y1)**2 <= r**2:\n",
    "                    ans[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isin(point,cycle):\n",
    "    l=(point[0]-cycle[0])**2+((point[1]-cycle[1])**2)\n",
    "    if l-cycle[2]**2>0:\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        jans=0\n",
    "        for i in queries:\n",
    "            for j in points:\n",
    "                if isin(j,i):\n",
    "                    jans+=1\n",
    "            ans.append(jans)\n",
    "            jans=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        for x, y, r in queries:\n",
    "            ans = 0\n",
    "            for a, b in points:\n",
    "                if (a - x) ** 2 + (b - y) ** 2 <= r * r:\n",
    "                    ans += 1  \n",
    "            res.append(ans)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        #枚举所有的点，计算与圆心的距离判断是否在圆内\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "\n",
    "        for i, (cx, cy, cr) in enumerate(queries):\n",
    "            for (px, py) in points:\n",
    "                if (cx - px) ** 2 + (cy - py) ** 2 <= cr ** 2:\n",
    "                    ans[i] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isin(point,cycle):\n",
    "    l=(point[0]-cycle[0])**2+((point[1]-cycle[1])**2)\n",
    "    if l-cycle[2]**2>0:\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        jans=0\n",
    "        for i in queries:\n",
    "            for j in points:\n",
    "                if isin(j,i):\n",
    "                    jans+=1\n",
    "            ans.append(jans)\n",
    "            jans=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def ok(a,b,x,y,r):\n",
    "            return (a-x)**2+(b-y)**2 <= r**2\n",
    "        ans = []\n",
    "        for x,y,r in queries:\n",
    "            ans.append(sum(ok(a,b,x,y,r) for a,b in points))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for x, y, z in queries:\n",
    "            圆点数 = 0\n",
    "            for i, j in points:\n",
    "                i, j = i-x, j-y\n",
    "                圆点数 += i*i + j*j <= z*z\n",
    "            append(圆点数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        length = len(queries)\n",
    "        res = {i: 0 for i in range(length)}\n",
    "        for index, querie in enumerate(queries):\n",
    "            for point in points:\n",
    "                d = ((point[0] - querie[0])**2 + (point[1] - querie[1])**2)\n",
    "                if d <= querie[2]**2:\n",
    "                    res[index] += 1\n",
    "        return list(res.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isInside(cycle, point):\n",
    "    return pow(pow(point[0] - cycle[0], 2) + pow(point[1] - cycle[1], 2), 1/2) <= cycle[2]\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        # 边界条件处理\n",
    "        if len(queries) == 0:\n",
    "            return []\n",
    "        if len(points) == 0:\n",
    "            return []\n",
    "        \n",
    "        def pointNum(c):\n",
    "            return len(list(filter(lambda p: isInside(c, p), points)))\n",
    "\n",
    "        return list(map(pointNum, queries))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        count = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            for point in points:\n",
    "                if (queries[i][0]-point[0])*(queries[i][0]-point[0]) + (queries[i][1]-point[1])*(queries[i][1]-point[1]) <= queries[i][2]*queries[i][2]:\n",
    "                    count[i] += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "        for p in points:\n",
    "            for i in range(len(queries)):\n",
    "                if (p[0]-queries[i][0])**2 + (p[1]-queries[i][1])**2 <= queries[i][2]**2:\n",
    "                    ans[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: list[list[int]], queries: list[list[int]]) -> list[int]:\n",
    "        res=[]\n",
    "        for C in queries:\n",
    "            tmp=0\n",
    "            for P in points:\n",
    "                if (P[0] - C[0])**2 + (P[1] - C[1])**2 <= C[2]**2:\n",
    "                    tmp+=1\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isin(point,cycle):\n",
    "    l=(point[0]-cycle[0])**2+((point[1]-cycle[1])**2)\n",
    "    if l-cycle[2]**2>0:\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        jans=0\n",
    "        for i in queries:\n",
    "            for j in points:\n",
    "                if isin(j,i):\n",
    "                    jans+=1\n",
    "            ans.append(jans)\n",
    "            jans=0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for x, y, z in queries:\n",
    "            圆点数 = 0\n",
    "            z *= z\n",
    "            for i, j in points:\n",
    "                圆点数 += (i-x)**2 + (j-y)**2 <= z\n",
    "            append(圆点数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def distance(a, b):\n",
    "            return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2\n",
    "        ans = []\n",
    "        for *a, r in queries:\n",
    "            r *= r\n",
    "            ans.append(0)\n",
    "            for b in points:\n",
    "                if distance(a, b) <= r:\n",
    "                    ans[-1] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        count = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            for point in points:\n",
    "                if (queries[i][0]-point[0])**2 + (queries[i][1]-point[1])**2 <= queries[i][2]**2:\n",
    "                    count[i] += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        if not queries:\n",
    "            return []\n",
    "        ans = [0]*len(queries)\n",
    "\n",
    "        for i,circle in enumerate(queries):\n",
    "            has_map = {}\n",
    "\n",
    "            x,y,r = circle\n",
    "            \n",
    "            for point in points:\n",
    "                point=tuple(point)\n",
    "                if point not in has_map:\n",
    "                    has_map[point] = ((point[0]-x)**2+(point[1]-y)**2)**(1/2)\n",
    "                \n",
    "                if has_map[point] <= r:\n",
    "                    ans[i]+=1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        points_a = defaultdict(int)\n",
    "        for x, y in points:\n",
    "            points_a[(x, y)] += 1\n",
    "\n",
    "        m, n = len(points_a), len(queries)\n",
    "        answer = []\n",
    "        for i in range(n):\n",
    "            result = 0\n",
    "            for pos, c in points_a.items():\n",
    "                sq_dist = (queries[i][0] - pos[0]) ** 2 + (queries[i][1] - pos[1]) ** 2\n",
    "                if sq_dist <= queries[i][2] ** 2:\n",
    "                    result += c\n",
    "            answer.append(result)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        count = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            for point in points:\n",
    "                if (queries[i][0]-point[0])**2 + (queries[i][1]-point[1])**2 <= queries[i][2]**2:\n",
    "                    count[i] += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (cx, cy, cr) in enumerate(queries):\n",
    "            for (px, py) in points:\n",
    "                if (cx - px) ** 2 + (cy - py) ** 2 <= cr ** 2:\n",
    "                    ans[i] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for x, y, z in queries:\n",
    "            圆点数 = 0\n",
    "            z *= z\n",
    "            for i, j in points:\n",
    "                圆点数 += (i-x)*(i-x) + (j-y)*(j-y) <= z\n",
    "            append(圆点数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answer=[]\n",
    "        for i in range(0,len(queries)):\n",
    "            cnt=0\n",
    "            r=queries[i][2]\n",
    "            y=queries[i][1]\n",
    "            x=queries[i][0]\n",
    "            for j in range(0,len(points)):\n",
    "                y_p=points[j][1]\n",
    "                x_p=points[j][0]\n",
    "                lenght=x-x_p\n",
    "                height=y-y_p\n",
    "                distance=lenght**2+height**2\n",
    "                if distance<=r**2:\n",
    "                    cnt+=1\n",
    "            answer.append(cnt)\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        def distance(x, y, r):\n",
    "            l1 = 0\n",
    "            for i in range(len(points)):\n",
    "                if((points[i][0] - x)**2 + (points[i][1] - y)**2 <= r**2):\n",
    "                    l1  = l1 + 1\n",
    "            return l1\n",
    "        l2 = []\n",
    "        for i in range(len(queries)):\n",
    "            x = queries[i][0]\n",
    "            y = queries[i][1]\n",
    "            r = queries[i][2]\n",
    "            re = distance(x, y, r)\n",
    "            l2.append(re)\n",
    "        return l2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for x, y, z in queries:\n",
    "            圆点数 = 0\n",
    "            for i, j in points:\n",
    "                i, j = i-x, j-y\n",
    "                圆点数 += i*i + j*j <= z*z\n",
    "            append(圆点数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        num_list = []\n",
    "        for item in queries:\n",
    "            temp_num = 0\n",
    "            for note in points:\n",
    "                dist = math.sqrt((note[0] - item[0]) ** 2 + (note[1] - item[1]) ** 2)\n",
    "                if dist <= item[2]:\n",
    "                    temp_num += 1\n",
    "            num_list.append(temp_num)\n",
    "\n",
    "        return num_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        返回数组 = []\n",
    "        append = 返回数组.append\n",
    "        for x, y, z in queries:\n",
    "            圆点数 = 0\n",
    "            z *= z\n",
    "            for i, j in points:\n",
    "                i, j = i-x, j-y\n",
    "                圆点数 += i*i + j*j <= z\n",
    "            append(圆点数)\n",
    "        return 返回数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right\r\n",
    "class Solution:\r\n",
    "    def countPoints(self, points: list[list[int]], queries: list[list[int]]) -> list[int]:\r\n",
    "        points.sort()\r\n",
    "        def query(x: int, y: int, r: int) -> int:\r\n",
    "            lo = bisect_left(points, x - r, key=lambda p: p[0])\r\n",
    "            hi = bisect_right(points, x + r, lo=lo, key=lambda p: p[0])\r\n",
    "            return sum(1 if (x - points[i][0]) ** 2 + (y - points[i][1]) ** 2 <= r ** 2 else 0 for i in range(lo, hi))\r\n",
    "        return [query(*q) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/env python3\n",
    "# -*- coding: utf-8 -*-\n",
    "# Xiang Wang <ramwin@qq.com>\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "特意用最差的算法\n",
    "一看, 才500个点, 直接遍历喽\n",
    "再一看, 都是整数, 可以考虑遍历圆里面的点或者遍历圆的边\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "from dataclasses import dataclass\n",
    "import math\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class Point:\n",
    "    \"\"\"点\"\"\"\n",
    "    x: int\n",
    "    y: int\n",
    "\n",
    "    def get_distance(self, target: \"Point\"):\n",
    "        # XXX 可以返回平方数, 用整数比较\n",
    "        return math.sqrt(\n",
    "            math.pow(self.x - target.x, 2)\n",
    "            + math.pow(self.y - target.y, 2)\n",
    "        )\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class Cycle(Point):\n",
    "    \"\"\"圆\"\"\"\n",
    "    r: int\n",
    "\n",
    "    def contain(self, point: Point):\n",
    "        return self.r >= self.get_distance(point)\n",
    "\n",
    "@dataclass\n",
    "class Map:\n",
    "    \"\"\"地图\"\"\"\n",
    "\n",
    "    points: List[Point]\n",
    "\n",
    "\n",
    "class SolutionBruteForce:\n",
    "    \"\"\"暴力搜索\"\"\"\n",
    "\n",
    "    def __init__(self, map_: Map, cycles: List[Cycle]):\n",
    "        self.map_ = map_\n",
    "        self.cycles = cycles\n",
    "\n",
    "    def get_result(self):\n",
    "        results = []\n",
    "        for cycle in self.cycles:\n",
    "            results.append(\n",
    "                self.get_include_point_cnt(cycle)\n",
    "            )\n",
    "        return results\n",
    "\n",
    "    def get_include_point_cnt(self, cycle):\n",
    "        result = 0\n",
    "        for point in self.map_.points:\n",
    "            if cycle.contain(point):\n",
    "                result += 1\n",
    "        return result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    适配leetcode\n",
    "    \"\"\"\n",
    "\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]):\n",
    "        solution = SolutionBruteForce(\n",
    "            map_=Map(\n",
    "                points=[\n",
    "                    Point(*point)\n",
    "                    for point in points\n",
    "                ],\n",
    "            ),\n",
    "            cycles=[\n",
    "                Cycle(*point)\n",
    "                for point in queries\n",
    "            ],\n",
    "        )\n",
    "        return solution.get_result()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        for x, y, radius in queries:\n",
    "            pointcount = 0\n",
    "            r = radius**2\n",
    "            for point in points:\n",
    "                if (point[0] - x)**2 + (point[1] - y)**2 <= r:\n",
    "                    pointcount += 1\n",
    "            answer.append(pointcount)\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        for query in queries:\n",
    "            pointcount = 0\n",
    "            x, y, radius = query[0], query[1], query[2]\n",
    "            r = radius * radius\n",
    "            for point in points:\n",
    "                disx = point[0] - x\n",
    "                disy = point[1] - y\n",
    "                if disx*disx + disy*disy <= r:\n",
    "                    pointcount += 1\n",
    "            answer.append(pointcount)\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ret = []\n",
    "\n",
    "        for q in queries:\n",
    "            counter = 0\n",
    "            for p in points:\n",
    "                distance = (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2\n",
    "                if distance <= q[2] ** 2:\n",
    "                    counter += 1\n",
    "            ret.append(counter)\n",
    "        print(ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        for x,y,r in queries:\n",
    "            points.sort(key = lambda a: (a[0]-x)**2+(a[1]-y)**2)\n",
    "            ans.append(bisect_right(points,r**2,key = lambda a: (a[0]-x)**2+(a[1]-y)**2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [0]*n\n",
    "        def inside(x, y, x_, y_, r):\n",
    "            if (x-x_)**2 + (y-y_)**2 <= r**2:\n",
    "                return True\n",
    "            return False\n",
    "        for i in range(len(points)):\n",
    "            for j in range(n):\n",
    "                if inside(points[i][0], points[i][1], queries[j][0], queries[j][1], queries[j][2]):\n",
    "                    ans[j] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        ans=[]\n",
    "        for x in queries:\n",
    "            tmp=0\n",
    "            for y in points:\n",
    "                if (x[0]-y[0])**2+(x[1]-y[1])**2 <= x[2]**2:\n",
    "                    tmp+=1\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPoints(\r\n",
    "        self, points: List[List[int]], queries: List[List[int]]\r\n",
    "    ) -> List[int]:\r\n",
    "        ans = [0] * len(queries)\r\n",
    "        for i in range(len(points)):\r\n",
    "            x, y = points[i]\r\n",
    "            for j in range(len(queries)):\r\n",
    "                x1, y1, radius = queries[j]\r\n",
    "                if (x - x1) ** 2 + (y - y1) ** 2 <= radius**2:\r\n",
    "                    ans[j] += 1\r\n",
    "\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        res=[]\n",
    "        for k in queries :\n",
    "            now=0\n",
    "            for x in points:\n",
    "                if (k[1]-x[1])**2+(k[0]-x[0])**2<=k[2]*k[2]:\n",
    "                    print(abs((k[1]-x[1])+(k[0]-x[0])))\n",
    "                    now+=1\n",
    "            res.append(now)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
